This invention relates to state machines, and in particular to reducing the power consumption of state machines which are implemented as a portion of an integrated circuit or in other formats.
A state machine, also known as a finite state machine, responds to events by moving from state to state according to a formal set of rules. These rules are typically customized for the particular problem to be solved. State machines can be used generally in any electronic system, for example, a general purpose computer system, a special purpose computer system, or a control system that control products such as home appliances or industrial products. The state machine typically includes three components: (1) a set of states, (2) a set of events, and (3) a mapping from each state or event to a corresponding action. This set of states requires that in any given time the machine be in a single state. The events are then actions which the machine recognizes. Typically, an event will represent an external input. The state machine, however, may also generate events internally which cause changes of state. Finally, the mapping from each state to a corresponding action means that the action may cause a transition to a different state, provide a particular output signal, or otherwise indicate transition to the successor state.
Computation by the state machine begins in the start state, but then the state machine will change to a new state caused by external signals provided to the state machine or an internal transition. There are many variants of state machines, for example, state machines can have actions or provide outputs which are based on transitions (Mealy machine) or based upon states (Moore machine). A state machine can be considered to be an abstract model of a system, for example, a physical, biological, mechanical, electronic, or software system.
A state machine can be used to model interaction between a system and its environment. Its state is a way of remembering what has occurred so far. A transition occurs when an event in the environment causes the system to change state. Given a sequence of inputs, a state machine will produce a sequence of outputs that is dependent upon the initial state, the transition function which maps each current state and input to a next state, and an output function that maps each current state to an output. In Moore machines the output is a function of only the current state, while in Mealy machines the output is a function of the current state and the input.
It has been common in integrated circuit technology since the 1980's for distributed state machines to be used rather than a central control engine. This has resulted primarily because of the availability of integrated circuit technology and increasing performance requirements. By distributing state machines across an integrated circuit with appropriate control points in appropriate locations, shorter electrical connections for critical paths results, improving performance.
In most state machines a control RAM or ROM allows programming the state machine. This memory typically loops in the same state waiting for an external signal to change or some internal condition to change to cause the state machine to transition to the next state. In many applications for state machines, because the speed of the integrated circuit is so fast in comparison to the external events triggering changes in state, a significant amount of time is spent in this idle loop. In this loop, usually the state machine keeps accessing the same memory location. This usually causes all of the bit lines to be precharged at the beginning of each clock cycle, and then the selected lines are discharged. In addition, other elements of the state machine may also need to be activated, further dissipating power. Because the output data remains the same, these actions dissipates unnecessary power.
What is needed is a state machine which can be operated in a manner so that when the input data has not changed, and therefore the state of the machine will not transition to a new state, power consumption is reduced.